package BackTracking;

import java.util.*;

/**
 * 描述
 * 给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
 * 例如，给出n=3，解集为：
 * "((()))", "(()())", "(())()", "()()()", "()(())"
 *
 * 数据范围：0 \le n \le 100≤n≤10
 * 要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)
 * 示例1
 * 输入：
 * 1
 * 返回值：
 * ["()"]
 * 示例2
 * 输入：
 * 2
 * 返回值：
 * ["(())","()()"]
 *
 * */
public class 括号生成 {
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    ArrayList<String> res = new ArrayList<String>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        if(n==0){
            return res;
        }
        //回溯法，生成多少个左括号，就生成多少个右括号
        backTrack("",n,n);
        return res;
    }

    //n1代表左可以生成的数量，n2代表右可以生成的数量
    private void backTrack(String str, int n1,int n2){
        //在树的过程中，发现左括号能有的个数比右括号多,说明此时的右括号一定比左括号多肯定不匹配
        if(n1>n2){
            return;
        }
        if(n1==0&&n2==0){
            //找到一组,添加结果
            res.add(str);
            return;
        }
        if(n1>0){
            backTrack(str+"(",n1-1,n2);
        }
        if(n2>0){
            backTrack(str+")",n1,n2-1);
        }


    }
}
